Information data communicated between a transmitter and receiver in a wireless system can be corrupted by various channel effects such as noise, fading, and multi-path effects. Thus, a technique applied at a transmitter known as error correction coding is typically employed to mitigate different effects of wireless communication channels. By introducing a redundancy in the transmission data, channel coding can reduce a probability that various channel effects will corrupt useful information. In most cases, the channel coding has been proven to be successful in different channel environments, and it is commonly adopted as a required part of the transmitter and receiver for different emerging communication standards.
Convolutional codes are error correction codes well-known in the art for mitigating different channel effects, such as noise and block fading. One kind of convolutional codes, which has been adopted as a standard for North American digital cellular radio communications, is known as IS-130 by the International Telecommunication Union. IS-130 employs a type of convolutional code known in the art as a tailbiting convolutional code (TBCC), in which encoding and decoding of information data are performed in a blockwise manner. The term tailbiting refers to the fact that encoder's starting and ending states are identical.
Although the decoder knows that the encoder begins and ends in the same encoding state, the decoder does not know the value of that state. Therefore, the initial encoding state is unknown to the decoder. Furthermore, an encoder may have started in any of possible encoding states with approximately equal probability. Hence, the main challenge for designing efficient TBCC decoder is that a decoder must be able to quickly and accurately determine the initial encoding state.
There are two types of tailbiting convolutional codes: the non-recursive and recursive codes. For a non-recursive (feed forward) TBCC, the encoder's shift registers may be initialized by the last K−1 information bits in reversed order, where K−1 is the number of encoder's memory elements, and K is the constraint length. Once the initialization is finished, the encoding process may start similarly to the conventional convolutional coding. For a recursive (feedback) TBCC, the encoding is performed twice. The first encoding process may be performed to find ending state of the input sequence. The starting state is all-zero state and the encoding process may be the same as that of conventional convolutional encoder. In the second stage, the encoder may be initialized with ending state obtained from the first encoding stage. Then, encoding may be applied to produce a TBCC encoded bit-sequence by using the same information bit-sequence as in the first encoding stage.
Encoding complexity of a non-recursive TBCC is the same as that of convolutional coding. However, encoding complexity of the recursive TBCC is doubled compared to the convolutional coding of the same constraint length. Since the non-recursive and recursive convolutional codes have similar error rate performance, the non-recursive codes are usually preferred. Each forward error correction (FEC) block may be encoded by utilizing a non-recursive TBCC encoder. This is achieved by initializing an encoder's memory with the last data bits of the FEC block that is being encoded.
The TBCC decoding based on a maximum-likelihood (ML) search of decoding states is an optimal decoding algorithm for tailbiting convolutional codes in terms of error correcting performance. This technique is based on the Viterbi Algorithm (VA) which enumerates all codewords and selects the most likely one. The decoder evaluates all possible starting states while knowing that the ending state is the same. For each starting state, the VA decoding is applied while the ending state is forced to be the same as the starting state. Therefore, the VA is utilized 2K-1 times, where K−1 is the number of memory elements in the TBCC decoder with constraint length of K. The decoder chooses the surviving path with the highest path metric (most likely path) out of 2K-1 paths.
Although the outcome is correct in most cases, the ML based TBCC decoding algorithm may be unacceptably complex and slow for many applications. The decoding time is always 2K-1 longer than that of the encoder's non-tailbiting counterpart. As a result, the ML based TBCC decoder may place great demands on computational resources.
Therefore, it is desirable to have an algorithm that achieves error correction performance close to that of ML based TBCC decoders, but with reduced computational complexity.